﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace LinkedList
{
    class Program
    {
        static void Main(string[] args)
        {
            LinkedList ll = new LinkedList();
            ll.AppendNode(3);
            ll.AppendNode(2);
            ll.AppendNode(6);
            ll.AppendNode(1);
            ll.AppendNode(4);
            ll.AppendNode(2);
            ll.AppendNode(5);
            ll.AppendNode(8);

            //ll.RemoveNode(5);
            ll.Display();

            //ll.SwapConsecutiveNodes();
            //ll.SwapInPairs();
            //ll.RemoveDuplicates();
            ll.NthFromLast(5);

            ll.Display();

            Console.ReadKey();
        }
    }

    public class LinkedList
    {
        public Node head = null;

        public void AppendNode(int data)
        {
            Node newNode = new Node(data);
            if (head == null)
                head = newNode;
            else
            {
                Node node = head;
                while (node.Next != null)
                    node = node.Next;
                node.Next = newNode;
            }
        }

        public void RemoveNode(int data)
        {
            Node node = head;
            if (node.data == data)
            {
                head = node.Next;
                return;
            }
            Node prevNode = node;
            while (node != null && node.data != data)
            {
                prevNode = node;
                node = node.Next;
            }
            if(node != null)
                prevNode.Next = node.Next;
        }

        public void Display()
        {
            Node node = head;
            while (node != null)
            {
                Console.Write(node.data + " ");
                node = node.Next;
            }
            Console.WriteLine();
        }

        public void SwapConsecutiveNodes()
        {
            Node node = head;
            Node t1 = node;
            while (node != null)
            {
                Node temp = node.Next;

                if (temp != null)
                {
                    Node t2 = temp.Next;
                    if (node == head)
                        head = Swap(node);
                    else
                        t1.Next = Swap(node);
                    t1 = node;
                    node = t2;
                }
                else
                    node = node.Next;
            }
        }

        private Node Swap(Node node)
        {
            Node t1 = node.Next;
            Node t2 = t1.Next;
            t1.Next = node;
            node.Next = t2;
            return t1;
        }

        public void SwapInPairs()
        {
            Node node = head, fNode = head;
            Node node2, node3, node4, pNode = head;
            while (node != null)
            {
                node2 = node.Next;
                node3 = node2.Next;
                node4 = node3.Next;
                node2.Next = node4.Next;
                node4.Next = node;
                if (head == fNode)
                    head = node3;
                else
                    pNode.Next = node3;
                pNode = node.Next;
                node = node2.Next;
            }
        }

        public void RemoveDuplicates()
        {
            Node t = head;
            Node s = null;
            Node prev = null;
            Node start = null;
            while (t != null)
            {
                prev = t;
                s = t.Next;
                start = s;
                while (s != null)
                {
                    if (s.data == t.data)
                    {
                        prev.Next = s.Next;
                        s = s.Next;
                    }
                    s = s.Next;
                    prev = s;
                }
                t.Next = s;
                t = s;
            }
        }

        internal void NthFromLast(int c)
        {
            Node t1 = head;
            Node t2 = head;
            while (--c > 0)
                t2 = t2.Next;
            while (t2.Next != null)
            {
                t1 = t1.Next;
                t2 = t2.Next;
            }
            Console.WriteLine(t1.data);
        }
    }

    public class Node
    {
        public Node Next {get; set;}
        public int data {get; set; }
        public Node(int n)
        {
            data = n;
            Next = null;
        }
    }
}
